package com.yiwenup.leetcode.offer;

import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
 **/
public class No031 {

    /**
     * 执行用时：3 ms, 在所有 Java 提交中击败了14.03%的用户
     * 内存消耗：41.2 MB, 在所有 Java 提交中击败了5.06%的用户
     */
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();

        int popIdx = 0;
        for (int p : pushed) {
            // 模拟入栈
            stack.push(p);
            while (!stack.isEmpty() && stack.peek().equals(popped[popIdx])) {
                stack.pop();
                popIdx++;
            }
        }

        return stack.isEmpty();
    }
}
